我要招人

去企业版

首页 > 试题广场 >

三个数的最大乘积

[编程题]三个数的最大乘积

热度指数：26286 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 $n$ 的无序数组 $A$ ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。

要求时间复杂度： $O(n)$ ，空间复杂度： $O(1)$ 。

数据范围：

$3 \le n \le 10^4$

$-10^4 \le A[i] \le 10^4$

示例1

输入

[3,4,1,2]

输出

算法知识视频讲解

Python 3

来牛客玩玩

class Solution:
    def solve(self , A: List[int]) -> int:
        # write code here
        A = sorted(A)
        # 两个负数 + 一个正数 / 三个正数
        return max(A[0]*A[1]*A[-1], A[-3]*A[-2]*A[-1])

发表于 2022-07-03 09:57:50 回复(0)

Python 3

给我吃一口西瓜

# 直接排序后 列出可能存在的几种可能
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最大乘积
# @param A int整型一维数组 
# @return long长整型
#
class Solution:
    def solve(self , A: List[int]) -> int:
        # write code here
        # 暴力,通过5/15
#         max=0
#         for i in range(len(A)):
#             for j in range(i+1,len(A)):
#                 for k in range(j+1,len(A)):
#                     temp= A[i]*A[j]*A[k]
#                     if temp > max:
#                         max=temp
#         return max
        if len(A)==3:
            return A[0]*A[1]*A[2]
        sortedA=sorted(A)
        MAX1=sortedA[-1]*sortedA[-2]*sortedA[-3]
        MAX2=sortedA[-1]*sortedA[-2]*sortedA[0]
        MAX3=sortedA[1]*sortedA[2]*sortedA[0]
        MAX4=sortedA[1]*sortedA[0]*sortedA[-1]
#         maxA=sortedA[len(A)-1]*sortedA[len(A)-2]*sortedA[len(A)-3]
#         minA=sortedA[0]*sortedA[1]*sortedA[2]
        return max(MAX1, MAX2, MAX3,MAX4)

发表于 2022-04-20 16:00:32 回复(0)

Python 3

danspace

class Solution:
    def solve(self , A: List[int]) -> int:
        # write code here
        A.sort()
        if A[0] >= 0:
            return A[-1]*A[-2]*A[-3]
        else:
            return max(A[0]*A[1]*A[-1], A[-1]*A[-2]*A[-3])

发表于 2022-04-19 16:49:49 回复(0)

Python 3

丿52赫兹丿

class Solution:
def solve(self , A: List[int]) -> int:
# write code here
A.sort(reverse=True)
if (A[2]>=0 and A[1]*A[2]>A[-1]*A[-2]) or A[0]<=0 :
return A[0]*A[1]*A[2]
else:
return A[0]*A[-1]*A[-2]

发表于 2022-02-08 10:51:04 回复(0)

Python 3

Joy_9

class Solution:
    def solve(self , A: List[int]) -> int:
        # write code here
        def quicksort(lists,i,j):
            if i>=j:
                return lists
            p=lists[i]
            low=i
            high=j
            while i<j:
                while i<j and lists[j]>=p:
                    j-=1
                lists[i],lists[j]=lists[j],lists[i]
                while i<j and lists[i]<=p:
                    i+=1
                lists[i],lists[j]=lists[j],lists[i]
            quicksort(lists,low,i-1)
            quicksort(lists,i+1,high)
            return lists
        n=len(A)
        lists=quicksort(A,0,n-1)
        
        return A[n-1]*A[n-2]*A[n-3] if A[n-1]*A[n-2]*A[n-3]>A[n-1]*A[0]*A[1] else A[n-1]*A[0]*A[1]

发表于 2022-01-06 05:14:45 回复(0)

Python 3

牛客111458759号

class Solution:
def solve(self , A: List[int]) -> int:
# write code here
A.sort()
return max(A[0] * A[1] * A[-1], A[-1] * A[-2] * A[-3])

发表于 2021-12-19 21:32:50 回复(0)

Python 3

条子在洗澡

class Solution:

def solve(self , A: List[int]) -> int:

if 0 in A:

A.remove(0)

b=sorted(A)

count1=0

if b[0] > 0 :

count=b[-1]*b[-2]*b[-3]

elif b[-1] < 0:

count=b[0]*b[1]*b[2]

else:

count=b[0]*b[1]*b[-1]

count1 = b[-1]*b[-2]*b[-3]

if count1 > count:

count = count1

return count

发表于 2021-11-02 17:05:31 回复(0)

Python 3

又要找工作了

要想找到最大乘积，对这个数组进行排序，如果最后一个数为正数，这个数组有可能存在负数，如果全为正数，则最大的三个数乘积就是排好序的最后三个相乘，如果存在负数，则一定是第一个数，第二个数，最后一个数相乘后与最后三个数相乘比较大小，如果最后一个数为负数，则最大的三个数乘积为排好序的最后三个数相乘。

class Solution:
    def solve(self , A ):
        # write code here
        A = sorted(A)
        max1 = A[-1]*A[-2]*A[-3]
        max2 = A[0]*A[1]*A[-1]
        return max(max1, max2)

发表于 2021-10-28 21:52:54 回复(0)

Python 3

饭扫光

先按照从大到小的顺序排序，选择前三位和后两位数据，对后两位数进行判断即可

class Solution:

def solve(self , A ):
A.sort(reverse = True)
length = len(A)
max_num= A[0]*A[1]*A[2]
if A[length-1]< 0 and A[length-2]< 0:
tmp_data = [abs(A[length-1]),abs(A[length-2])]
count = 0
for i in tmp_data:
if i>A[0] or i>A[1] or i>A[2]:
count += 1
if count == 2:
return A[0]*A[length-1]*A[length-2]
return max_num

发表于 2021-10-17 16:38:56 回复(0)

Python 3

Cantle

class Solution:
    def solve(self , A ):
        # write code here
        A.sort(reverse=True)
        return max(A[0]*A[1]*A[2],A[0]*A[-1]*A[-2])

降序排序，最大乘积可能为前三个最大的数相乘或者第一个最大的数和最后两个最小的负数（负负得正）

发表于 2021-10-13 12:23:51 回复(0)

Python 3

牛客963717697号

我那麼短，為什麼佔用那麼多內存呢？

class Solution:
    def solve(self , A ):
        A.sort(reverse = True)
        if A[-1] >= 0&nbs***bsp;A[0] <= 0&nbs***bsp;A[0]*A[1]*A[2] > A[-1]*A[-2]*A[0]:
            return A[0]*A[1]*A[2]
        return A[-1]*A[-2]*A[0]

发表于 2021-09-21 15:57:38 回复(0)

Python 3

个么

class Solution:
    def solve(self , A ):
        A.sort()
        return max(A[0]*A[1]*A[-1],A[-1]*A[-2]*A[-3])

发表于 2021-09-18 13:21:27 回复(0)

Python 3

Demo_mo

class Solution:
def solve(self , A ):
# write code here
temp = A[0]*A[1]*A[2]
for i in range(len(A)):
for j in range(i+1,len(A)):
for k in range(j+1,len(A)):
if A[i]*A[j]*A[k] > temp:
temp = A[i]*A[j]*A[k]

return temp

超时了

发表于 2021-08-28 15:59:55 回复(1)

Python 3

一棵草

class Solution:
def solve(self , A ):
# write code here
A.sort()
#print(A)
if A[-1]*A[-2]*A[-3] >= A[0]*A[1]*A[-1]:
return A[-1]*A[-2]*A[-3]
else:
return A[0]*A[1]*A[-1]

发表于 2021-08-15 05:16:21 回复(0)

Python 3

Stephenling

class Solution:
def solve(self , A ):
# write code here
B = A.copy()
max1 = max(B)
B.remove(max1)
max2 = max(B)
B.remove(max2)
max3 = max(B)

min1 = min(A)
A.remove(min1)
min2 = min(A)

if max1 * max2 * max3 > max1 * min1 * min2:
return max1 * max2 * max3
else:
return max1 * min1 * min2

发表于 2021-08-10 22:24:43 回复(0)

Python 3

牛客447641769号

#
# 最大乘积
# @param A int整型一维数组
# @return long长整型
#
class Solution:
def solve(self , A ):
# write code here
# 先排序。取整数最大的三个积，或者最大两个负数以及最大正数积
A.sort()
return max(A[-1]*A[-2]*A[-3], A[0]*A[1]*A[-1])

发表于 2021-07-23 22:59:27 回复(0)